package com.spd.sort;
/**
 * 找到数组的最大值，最小值。
 * 因为在正常的情况下，是遍历和比较两次，每个值分别和最大、
 * 最小值进行对比。在此算法下，是数组每两两对比。然后小的和最小值做对比，
 * 大的和最大值做对比，这样，比较次数为3，之前的算法是每个元素分别和最大，
 * 最小值做比较，所以两个元素总计比较次数为4，
 * @author xianchao
 *
 */
public class MinMaxNum {

	private int[] array = null;
	
	private int max = Integer.MIN_VALUE;
	
	private int min = Integer.MAX_VALUE;
	
	public void init(int[] array) {
		this.array = array;
	}
	
	/**
	 * 分为两种情况，
	 * 第一种，数组有偶数个，则首先在前两个要素中找到最大、最小元素。然后在比较余下的
	 * 第二种，数组有奇数个，则把第一个要素同时设置成最大、最小。然后在比较余下的
	 */
	public void findMaxMin() {
		//1. 数组长度为0的不处理
		if(array.length == 0) {
			return;
		}
		int startIndex = 0;
		if(array.length % 2 == 1) {//2. 奇数个
			max = array[0];
			min = array[0];
			startIndex = 1;
		} else {
			if(array[0] > array[1]) {//3. 偶数个
				max = array[0];
				min = array[1];
			} else {
				max = array[1];
				min = array[0];
			}
			startIndex = 2;
		}
		//4. 剩下的两两比较，比较结果中，较大的和max对比，较小的和min对比
		for(int i = startIndex; i < array.length - 1; i++) {
			int tempMax = 0, tempMin = 0;
			if(array[i] > array[i + 1]) {
				tempMax = array[i];
				tempMin = array[i + 1];
			} else {
				tempMax = array[i + 1];
				tempMin = array[i];
			}
			if(max < tempMax) {
				max = tempMax;
			}
			if(min > tempMin) {
				min = tempMin;
			}
		}
		System.out.println("max:" + max + ", min:" + min);
	}
	
	public static void main(String[] args) {
		MinMaxNum minMaxNum = new MinMaxNum();
//		int[] array = new int[]{1};
//		int[] array = new int[]{1, 1};
//		int[] array = new int[]{10, 9, 23, 15, 35, 24, 17, 21};
		int[] array = new int[]{10, 9, 23, 15, 35, 24, 17, 21, 1};
		minMaxNum.init(array);
		minMaxNum.findMaxMin();
	}
}
